package com.qjc.demo.algorithm.LRUOf自定义;

import java.util.HashMap;
import java.util.Map;

/**
 * 使用哈希表+双向链表的方式实现LRU算法
 *
 * @ClassName: LRUCache
 * @Author: qjc
 * @Date: 2023/8/29 23:37
 */
public class LRUCache {
    // 定义双向链表节点类
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 定义Hash表
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    // 定义除了插入Hash表中数据条数
    private int size;
    // 定义Hash表的容量大小，后续判断是否超出容量来做尾结点删除
    private int capacity;
    // 定义一个头尾结点
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 定义一个伪头部和伪尾部，主要是为了不越界，所有的操作都在这两个节点中间进行
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }


    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 把该节点放到链表头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果key不存在，则将该节点插入到链表头部
            DLinkedNode dLinkedNode = new DLinkedNode(key, value);
            addHead(dLinkedNode);
            cache.put(key, dLinkedNode);
            ++size;
            if (size > capacity) {
                // 如果大于hash表容量则删除尾部节点
                DLinkedNode tail = removeTail();
                // 删除尾结点对应的Hash表中的数据
                cache.remove(tail.key);
                --size;
            }
        } else {
            // 如果key已存在，则更新value值，并把该节点转移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    // 删除尾结点
    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }

    public void moveToHead(DLinkedNode node) {
        // 删除该节点
        removeNode(node);
        // 将该节点插入头部
        addHead(node);
    }

    // 删除节点
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点添加到链表头部
    public void addHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));

    }

}
